/*
 * MIT License
 *
 * Copyright (c) 2019 Mr.css
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 */

package cn.seaboot.commons.lang;

import cn.seaboot.commons.core.CommonUtils;
import cn.seaboot.commons.exception.BizException;
import org.jetbrains.annotations.NotNull;

import javax.annotation.Nullable;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * list -> tree 转换工具
 * <p>
 * E.G.:
 * <pre>
 *      List<Map<String,Object>> tree = new TreeBuilder()
 *          .setList(list)
 *          .groupBy()
 *          .getByMinPid();
 * </pre>
 * <p>
 * 注意：如果父节点如果为 null，通常属于根节点，算法上也是这么判断的。
 * <p>
 * 短板：受限于泛型的语法，父子级格式不一致的场景，很多函数会用得很难受
 *
 * @author Mr.css
 * @version 2020-07-06 11:18
 * @see cn.seaboot.commons.core.TreeBuilder
 */
public class TreeBuilder {

    /**
     * 父级
     */
    private List<TreeNode> parents;

    /**
     * 子级
     */
    private List<TreeNode> children;

    /**
     * 父节点列表
     *
     * @param p parent-list
     * @return this
     */
    public TreeBuilder setParents(List<TreeNode> p) {
        this.parents = p;
        return this;
    }

    /**
     * 父节点列表
     *
     * @param c children-list
     * @return this
     */
    public TreeBuilder setChildren(List<TreeNode> c) {
        this.children = c;
        return this;
    }

    /**
     * 映射父节点列表
     *
     * @param p parent-list
     * @return this
     */
    public <T> TreeBuilder setParents(List<T> p, Function<T, TreeNode> mapper) {
        List<TreeNode> sub = p.stream().map(mapper).collect(Collectors.toList());
        return this.setParents(sub);
    }

    /**
     * 映射父节点列表
     *
     * @param p parent-list
     * @return this
     */
    public <T> TreeBuilder setChildren(List<T> p, Function<T, TreeNode> mapper) {
        List<TreeNode> sub = p.stream().map(mapper).collect(Collectors.toList());
        return this.setChildren(sub);
    }


    /**
     * 获取列表
     *
     * @return 树形节点列表
     */
    public List<TreeNode> getParents() {
        return this.parents;
    }

    /**
     * 获取列表
     *
     * @return 树形节点列表
     */
    public List<TreeNode> getChildren() {
        return this.children;
    }

    /**
     * 数据分组
     *
     * @return TreeBuilder
     */
    public TreeBuilder groupBy() {
        if (CommonUtils.isEmpty(parents)) {
            throw new IllegalArgumentException("Child list and parent list are both empty!");
        }

        if(this.children == null) {
            this.children = this.parents;
        }

        for (TreeNode p : parents) {
            for (TreeNode c : children) {
                // 此处可能发生空指针，注意初始化集合
                if (p.getId().equals(c.getPid())) {
                    // 子节点指向父节点
                    c.setParent(p);

                    // 父节点指向子节点
                    List<TreeNode> list = p.getChildren();
                    if (CommonUtils.isEmpty(list)) {
                        list = new ArrayList<>();
                        p.setChildren(list);
                    }
                    list.add(c);
                }
            }
        }
        return this;
    }

    /**
     * 如果已知要取的节点，直接按照节点 pid 进行获取
     *
     * @param pid 值允许为 null，因为数据库可能用 null 值表示顶级节点
     * @return tree
     */
    public List<TreeNode> getNodesByPid(@Nullable String pid) {
        List<TreeNode> res = new ArrayList<>();
        if (pid == null) {
            for (TreeNode p : parents) {
                if (p.getPid() == null) {
                    res.add(p);
                }
            }
        } else {
            for (TreeNode p : parents) {
                if (pid.equals(p.getPid())) {
                    res.add(p);
                }
            }
        }
        return res;
    }


    /**
     * 根据 id 查找第一个满足条件的节点
     *
     * @param id id 值不允许为空
     * @return 节点
     */
    public TreeNode getNodeById(@NotNull String id) {
        for (TreeNode p : parents) {
            // 故意的：如果 id 为 null 会提前报错
            if (id.equals(p.getId())) {
                return p;
            }
        }
        return null;
    }

    /**
     * 从结果集中取出 pid 最小的数据
     * <p>
     * 特例：如果存在 pid 为 null 的数据，则将该数据，作为最小的数据
     *
     * @return tree
     */
    public List<TreeNode> getByMinPid() {
        String min = parents.get(0).getPid();
        String pid;
        for (TreeNode p : parents) {
            pid = p.getPid();
            if (pid == null) {
                return this.getNodesByPid(null);
            } else {
                if (pid.compareTo(min) < 0) {
                    min = pid;
                }
            }
        }
        return this.getNodesByPid(min);
    }

    /**
     * 从组装的结果中取出Pid最大的数据
     * <p>
     * 特例：如果存在 pid 为 null 的数据，则将该数据，作为最大的数据
     *
     * @return tree
     */
    public List<TreeNode> getByMaxPid() {
        String max = parents.get(0).getPid();
        String pid;
        for (TreeNode p : parents) {
            pid = p.getPid();
            if (pid == null) {
                return this.getNodesByPid(null);
            } else {
                if (pid.compareTo(max) > 0) {
                    max = pid;
                }
            }
        }
        return this.getNodesByPid(max);
    }

    /**
     * 随机取出一个元素，反复遍历树，直到取出最顶级的父节点。
     * <p>
     * 树状结构越深，需要遍历的次数越多。
     *
     * @return tree
     */
    public List<TreeNode> getRoot() {
        // 以第一个节点的 pid 作为顶级节点，不断递归检索
        TreeNode top = parents.get(0);

        // 声明一个 list 记录已经查找过的节点，避免出现无限递归
        List<String> list = new ArrayList<>();
        list.add(top.getPid());

        while (top.hasParent()) {
            top = top.getParent();
            if (list.contains(top.getPid())) {
                // 出现无限递归的数据，异常退出
                throw new BizException("Circular dependencies：" + top);
            } else {
                // 继续下一次递归检索
                list.add(top.getPid());
            }
        }
        return this.getNodesByPid(top.getPid());
    }
}
